package org.gzc.search;

import java.util.List;

/**
 * @Description: 插值查找
 * int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);
 * @Author: guozongchao
 * @Date: 2020/8/11 16:40
 */
public class InsertValueSearch implements SearchStrategy{
    @Override
    public int searchOne(int[] array, int key) {
        return searchOne(array,0,array.length-1,key);
    }

    @Override
    public List<Integer> searchMore(int[] array, int key) {
        return null;
    }

    //递归版本的二分查找
    public int searchOne(int[] array, int left, int right, int key) {
        //注意：findVal < arr[0] 和 findVal > arr[arr.length - 1] 必须需要
        // 否则我们得到的 mid 可能越界
        if (left > right || key < array[0] || key > array[array.length - 1]) {
            return -1;
        }

        // 求出 mid, 自适应
        int mid = left + (right - left) * (key - array[left]) / (array[right] - array[left]);

        if (array[mid] > key) {
            return searchOne(array, left, mid - 1, key);
        } else if (array[mid] < key) {
            return searchOne(array, mid + 1, right, key);
        } else {
            return mid;
        }
    }
}
